package _2022.hot100._85_最大矩形;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-04-21 21:18
 */
public class Solution {

    // 单调栈
    public int maximalRectangle3(char[][] matrix){
        int m=matrix.length;
        if(m==0){
            return 0;
        }
        int n=matrix[0].length,ans=0;
        int[][] left=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    left[i][j]=(j==0?0:left[i][j-1])+1;
                }
            }
        }
        for(int j=0;j<n;j++){ // 对于每一列，使用基于柱状图的方法
            int[] up=new int[m];
            int[] down=new int[m];
            Deque<Integer> stack=new LinkedList<>();
            for(int i=0;i<m;i++){
                while(!stack.isEmpty()&&left[stack.peek()][j]>=left[i][j]){
                    stack.pop();
                }
                up[i]=stack.isEmpty()?-1:stack.peek();
                stack.push(i);
            }
            stack.clear();
            for(int i=m-1;i>=0;i--){
                while(!stack.isEmpty()&&left[stack.peek()][j]>=left[i][j]){
                    stack.pop();
                }
                down[i]=stack.isEmpty()?m:stack.peek();
                stack.push(i);
            }

            for(int i=0;i<m;i++){
                int height=down[i]-up[i]-1;
                int area=height*left[i][j];
                ans=Math.max(ans, area);
            }
        }
        return ans;
    }

    // 19ms
    public int maximalRectangle2(char[][] matrix){
        int ans=0;
        int r=matrix.length,c=matrix[0].length;
        int[][] left=new int[r][c];
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(matrix[i][j]=='1'){
                    left[i][j]=(j==0?0:left[i][j-1])+1;
                }
            }
        }

        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(matrix[i][j]=='0'){
                    continue;
                }
                int width=left[i][j];
                int area=width;
                for(int k=i-1;k>=0;k--){
                    width=Math.min(width, left[k][j]);
                    area=Math.max(area, width*(i-k+1));
                }
                ans=Math.max(ans, area);
            }
        }
        return ans;
    }
    // 动态规划 87ms
    public int maximalRectangle(char[][] matrix){
        int ans=0;
        int r=matrix.length,c=matrix[0].length;
        List[][] dp=new List[r][c];
        List<Integer> list=new ArrayList<>();
        if(matrix[0][0]=='1'){
            list.add(0,1);
            list.add(1,1);
            dp[0][0]=list;
            ans=1;
        }else{
            list.add(0,0);
            list.add(1,0);
            dp[0][0]=list;
        }
        for(int i=1;i<r;i++){
            List<Integer> tmp=new ArrayList<>();
            if(matrix[i][0]=='1'){
                tmp.add(0, 1);
                tmp.add(1,1+(int)dp[i-1][0].get(1));
                ans=Math.max(ans, Math.max(tmp.get(0), tmp.get(1)));
                dp[i][0]=tmp;
            }else{
                tmp.add(0, 0);
                tmp.add(1,0);
                dp[i][0]=tmp;
            }
        }

        for(int i=1;i<c;i++){
            List<Integer> tmp=new ArrayList<>();
            if(matrix[0][i]=='1'){
                tmp.add(0, 1+(int)dp[0][i-1].get(0));
                tmp.add(1,1);
                ans=Math.max(ans, Math.max(tmp.get(0), tmp.get(1)));
                dp[0][i]=tmp;
            }else{
                tmp.add(0, 0);
                tmp.add(1,0);
                dp[0][i]=tmp;
            }
        }
        for(int i=1;i<r;i++){
            for(int j=1;j<c;j++){
                List<Integer> tmp=new ArrayList<>();
                if(matrix[i][j]=='1'){
                    int hArea=1+(int)dp[i][j-1].get(0);
                    int vArea=1+(int)dp[i-1][j].get(1);
                    tmp.add(0, hArea);
                    tmp.add(1, vArea);
                    if(matrix[i-1][j]=='1'&&matrix[i][j-1]=='1'&&matrix[i-1][j-1]=='1'){
                        //固定宽
                        int width=1+Math.min((int)dp[i][j-1].get(0),(int)dp[i-1][j].get(0)-1);
                        int height=(int)dp[i-1][j].get(1);
                        for(int k=j-1;k>=j-width+1;k--){
                            height=Math.min(height,(int)dp[i][k].get(1)-1);
                        }
                        height+=1;
                        ans=Math.max(ans,Math.max(hArea, Math.max(vArea, width*height)));
                        //固定高
                        width=(int)dp[i][j-1].get(0);
                        height=1+Math.min((int)dp[i][j-1].get(1)-1,(int)dp[i-1][j].get(1));
                        for(int k=i-1;k>=i-height+1;k--){
                            width=Math.min(width, (int)dp[k][j].get(0)-1);
                        }
                        width+=1;
                        ans=Math.max(ans, Math.max(hArea, Math.max(vArea, width*height)));
                    }else{
                        ans=Math.max(ans,Math.max(hArea, vArea));
                    }
                    dp[i][j]=tmp;
                }else{
                    tmp.add(0, 0);
                    tmp.add(1,0);
                    dp[i][j]=tmp;
                }

            }
        }


        return ans;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maximalRectangle(new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','1','1','1'}}));
        System.out.println(s.maximalRectangle(new char[][]{{'1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','0'},{'1','1','1','1','1','1','1','0'},{'1','1','1','1','1','0','0','0'},{'0','1','1','1','1','0','0','0'}}));
    }
}
